package main.leetcode.clockin.May;

/**
 * 76.最小覆盖子串
 *
 * <p>给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
 *
 * <p>示例：输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"
 *
 * <p>说明：如果 S 中不存这样的子串，则返回空字符串 ""。 如果 S 中存在这样的子串，我们保证它是唯一的答案。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-window-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day23 {
    public static void main(String[] args) {
        //        System.out.println(new day23().minWindow("ADOBECODEBANC", "ABC"));
        //        System.out.println(new day23().minWindow("bba", "aa"));
        System.out.println(new day23().minWindow("a", "a"));
    }

    public String minWindow(String s, String t) {
        if ("".equals(t) || "".equals(s) || s.length() < t.length()) {
            return "";
        }
        // 记录所需char的个数
        int[] needs = new int[128];
        // 记录当前窗口中各char的个数
        int[] windows = new int[128];
        for (char c : t.toCharArray()) {
            ++needs[c];
        }

        int left = 0, right = 0;
        // 记录当前包含t中字符的长度
        int count = 0;
        // 记录结果子串的左右边界
        int resLeft = 0, resRight = s.length();
        char cur;
        boolean flag = false;
        while (right < s.length()) {
            cur = s.charAt(right);
            ++windows[cur];
            if (needs[cur] > 0 // 是t中字符
                    && needs[cur] >= windows[cur]) { // 当前窗口包含该字符数量不足
                ++count;
            }

            // 当包含所有目标字符
            while (count == t.length()) {
                flag = true;
                cur = s.charAt(left);
                // 缩小窗口，移动left，直到不满足包含所有目标字符
                // 判断方法与外层while相同
                if (needs[cur] > 0 && needs[cur] >= windows[cur]) {
                    --count;
                }
                if (right + 1 - left < resRight - resLeft) {
                    resLeft = left;
                    resRight = right + 1;
                }
                --windows[cur];
                ++left;
            }
            ++right;
        }
        return flag ? s.substring(resLeft, resRight) : "";
    }
}
